#include <limits.h>

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

// struct TreeNode
// {
//   int val;
//   TreeNode *left;
//   TreeNode *right;
//   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };

class Solution
{
 public:
  // 1.两数之和 unordered_map方法
  vector<int> twoSum(vector<int>& nums, int target)
  {
    std::unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++)
    {
      auto iter = map.find(target - nums[i]);
      if (iter != map.end())
      {
        return {iter->second, i};
      }
      // map.emplace(nums[i],i); // map[key=value, 本题 key：nums[i], value:索引i
      map[nums[i]] = i;
    }
    return {};
  }

  // 1.两数之和 双指针方法
  /**
   * @brief 三数之和调用
   *
   * @param nums
   * @param start
   * @param end
   * @param target
   * @param value : 先确定的一个数，再调用两数之和twoSum2()解决两数之和的问题
   * @return vector<vector<int>>
   */
  vector<vector<int>> twoSum2(vector<int>& nums, int start, int end, int target, int value)
  {
    vector<vector<int>> answer;
    while (start < end)
    {
      int sum = nums[start] + nums[end];
      if (sum == target)
      {
        vector<int> result;
        result.push_back(value);
        result.push_back(nums[start]);
        result.push_back(nums[end]);
        answer.push_back(result);
        // 继续往下找，因为要找所有的
        while (start < end && nums[start] == nums[start + 1])
        {
          start++;  // 避免重复
        }
        start++;

        while (start < end && nums[end] == nums[end - 1])
        {
          end--;
        }
        end--;
      }
      else if (sum < target)
      {
        start++;
      }
      else if (sum > target)
      {
        end--;
      }
    }
    return answer;
  }

  // 15.三数之和
  vector<vector<int>> threeSum(vector<int>& nums)
  {
    vector<vector<int>> answer;
    sort(nums.begin(), nums.end());
    int size = nums.size();
    for (int i = 0; i < size; i++)
    {
      if (i > 0 && nums[i] == nums[i - 1])
      {
        continue;
      }
      // a+b+c=0
      auto result = twoSum2(nums, i + 1, size - 1, -nums[i], nums[i]);
      answer.insert(answer.end(), result.begin(), result.end());
    }
    return answer;
  }

  // 560.和为k的子数组 暴力法:先固定左边界，然后枚举右边界
  int subarraySum(vector<int>& nums, int k)
  {
    int len = nums.size();
    int count = 0;
    for (int left = 0; left < len; left++)
    {
      int sum = 0;
      for (int right = left; right < len; right++)
      {
        sum += nums[right];

        if (sum == k)
        {
          count++;
        }
      }
    }
    return count;
  }
  // 560.和为k的子数组 前缀和：构建前缀和数组，以快速计算区间和
  // 前缀和这个思路，结合hash_map去做优化
  // 一看到这种题，凡是可以用前缀和节约累加（累异或、累乘等）运算的，都用前缀和。写完前缀和，
  // 验证没有边界错误，再加哈希搞定！O(N³)暴力解？反正我是不会去尝试的，肯定罚时5分钟。
  int subarraySum2(vector<int>& nums, int k)
  {
    int len = nums.size();
    // 计算前缀和的数组
    vector<int> preSum(len + 1);
    for (int i = 0; i < len; i++)
    {
      preSum[i + 1] = preSum[i] + nums[i];
    }

    int count = 0;
    for (int left = 0; left < len; left++)
    {
      for (int right = left; right < len; right++)
      {
        // 区间和 [left..right]，注意下标偏移
        if (preSum[right + 1] - preSum[left] == k)
        {
          count++;
        }
      }
    }
    return count;
  }

  // 禾赛科技：最小子串和，最小子串和序列的第一个元素和最后一个元素的序列
  pair<int, int> findMinSum(vector<int>& nums)
  {
    int size = nums.size();                // size是原数组的尺寸
    vector<int> arr_sum(nums.size() + 1);  // 前缀和

    // arr_sum[0] = 0;
    for (int i = 0; i < size; i++)
    {
      arr_sum[i + 1] = arr_sum[i] + nums[i];
    }
    pair<int, int> q;
    int min = 0;
    // 遍历前缀和的数组
    for (int i = 0; i < size; i++)
    {
      for (int j = i; j < size; j++)
      {
        // 区间和[i,j]
        int sum = arr_sum[j + 1] - arr_sum[i];
        if (sum < min)
        {
          min = sum;
          q.first = i;
          q.second = j;
        }
      }
    }
    return q;
  }

  // 152.乘积的最大子数组
  // 这种方式不好，因为有0的存在
  int maxProduct(vector<int>& nums)
  {
    int size = nums.size();

    vector<int> arr_product(nums.size() + 1);  // 前缀乘积
    arr_product[0] = 1;
    for (int i = 0; i < size; i++)
    {
      arr_product[i + 1] = arr_product[i] * nums[i];
    }

    int max_product = 1;

    // 遍历前缀乘积的数组
    for (int i = 0; i < size; i++)
    {
      for (int j = i; j < size; j++)
      {
        // 区间乘积[i,j]
        int product = arr_product[i] == 0 ? 0 : (arr_product[j + 1] / arr_product[i]);
        if (product > max_product)
        {
          max_product = product;
        }
      }
    }

    return max_product;
  }
};

int main()
{
  Solution solute;
  vector<int> nums = {2, 3, -2, 4};
  solute.maxProduct(nums);
  // int target = 9;
  // int k = 2;
  // string s = "aab";
  // auto res = solute.subarraySum2(nums, k);

  return 0;
}